#ifndef LEETCODE_CN_CPP_PROBLEMS_1017_H
#define LEETCODE_CN_CPP_PROBLEMS_1017_H

#include <algorithm>
#include <string>
using namespace std;

namespace problem_1017
{

class Solution
{
private:
    bool isRepeated(const string &str, const string &sub)
    {
        auto strLen = str.length(), subLen = sub.length();
        if (subLen == 0 || subLen > strLen)
        {
            return false;
        }
        auto i = 0, j = 0;
        for (i = 0; i < strLen; ++i)
        {
            if (str[i] != sub[j])
            {
                return false;
            }
            j = (j + 1) % subLen;
        }
        return true;
    }

public:
    string gcdOfStrings(string str1, string str2)
    {
        auto subLen = __gcd(str1.length(), str2.length());
        auto sub = str1.substr(0, subLen);
        if (isRepeated(str1, sub) && isRepeated(str2, sub))
        {
            return move(sub);
        }
        return {};
    }
};

} // namespace problem_1017

#endif //LEETCODE_CN_CPP_PROBLEMS_1017_H